静5青年讲座回顾 | 黄昕博士谈从家务分配到工作调度的规约
关键词：静5青年讲座
编者按
2023年10月25日，Technion 的黄昕博士访问北京大学前沿计算研究中心，并在静园五院作了题为“A Reduction from Chores Allocation to Job Scheduling”的报告，介绍了他与合作者近期在计算经济学领域中公平分配方面所做的研究。此次报告由中心助理教授姜少峰老师主持。
黄昕博士报告现场
公平分配与我们的日常生活息息相关。黄博士此次报告围绕家务分配（chores allocation）中的公平分配进行展开。具体地，家务分配的基本模型阐述如下：每一件家务是不可分割的；每一个代理对于不同的家务都有自己的效益函数且效益函数满足可加性。之后，黄博士又进一步阐述了关于公平的两种定义方式：第一种（envy based fairness）是每个代理从自己的视角来看，自己所拿到的家务的效益是最好的（即每个代理需要承担的家务劳动是最少的）；第二种（share based fairness）是每个代理都与某个基准进行比较，使得每个代理对自己所拿到的家务感到满意。
此次报告中，黄博士基于第二种公平性（maximin share, MMS）家务分配讲解了他们的研究工作。首先，黄博士阐述了关于 MMS 家务分配的相关结果，在他们的工作之前，关于上述问题的最好近似比为11/9，而他们的工作将这一结果改进到了13/11。在介绍他们的工作之前，黄博士阐述了一个重要引理，该引理表明，对于 MMS 设定下的分配只需要研究 IDO（identical ordering）实例即可。
基于 IDO 实例，黄博士从 HFFD 算法谈起，表明基于MMS的家务分配与工作调度（job scheduling）存在某种关联（实际上最经典的工作调度问题是基于 MMS 的家务分配的一种特殊情况）。而针对工作调度已存在广泛研究，并且有相关紧的近似比，因此黄博士和其合作者试图将家务分配归约到工作调度问题，并期望能得到和工作调度问题相关的近似比。
之后，黄博士向大家阐述了如何实现从家务分配到工作调度的规约。其中需要重点考虑以下两个方面：一是如何将每个代理的效益函数归约到同一个视角的效益函数；二是针对家务分配问题的输出结果在工作调度问题中可能是非法输出这一情况如何进行相应调整。最终得到当近似比大于等于8/7时，总是可以实现家务分配到工作调度的规约。由于上述结果都是存在性结果，黄博士进一步向大家阐述了他们可以得到一个多项式时间的算法，且该结果是 FPTAS 的。
报告最后，黄博士又给出了相关的开放性问题。黄博士的汇报引起了在座老师同学们的积极提问，此次报告在热烈的讨论氛围中结束。
合影留念
图文 | 高贵晨
往期讲座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。